package demo.algorithm;


import org.junit.Before;
import org.junit.Test;

public class LinkedListDemo {

    StringNode link;

    @Before
    public void setUp() throws Exception {
        link = new StringNode("a");
        link.add("b");
        link.add("c");
        link.add("d");
        link.add("e");
        link.add("f");
        link.add("g");
        System.out.println("初始化：" + link);
    }

    @Test
    public void testToStr() {
        System.out.println(link.toString());
    }

    /**
     * 整体链表翻转
     */
    @Test
    public void testListReserve() {
        StringNode reversed = StringNode.reverse(link);
        System.out.println("执行结果：" + reversed);
    }

    /**
     * 指定区间翻转
     */
    @Test
    public void testReserveBetween() {
        StringNode.reverseBetween(link, 2, 50);
        System.out.println("执行结果：" + link);
    }

    @Test
    public void testMerge() {
        StringNode link1 = new StringNode("1");
        link1.add("3");
        link1.add("5");
        System.out.println(link1);

        StringNode link2 = new StringNode("2");
        link2.add("4");
        link2.add("6");
        System.out.println(link2);

        StringNode merged = StringNode.merge(link1, link2);
        System.out.println(merged);
    }

}

/**
 * 链表节点
 */
class StringNode {
    private String value;
    private StringNode next = null;


    public StringNode(String val) {
        this.value = val;
    }

    /**
     * 翻转链表：在遍历链表时，将当前节点的next 指针改为指向前一个节点。
     * 由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。
     * 最后返回新的头引用。
     *
     * @param head
     * @return
     */
    public static StringNode reverse(StringNode head) {
        if (head == null || head.next() == null) {
            return head;
        }
        StringNode prev = null;
        StringNode current = head;
        StringNode next = null;

        while (current != null) {
            next = current.next();  // 保存下一个节点
            // 开始翻转
            current.next(prev);  // 反转当前节点的指针
            prev = current;       // prev指针后移
            current = next;       // current指针后移
            System.out.println("执行过程：" + prev);
        }
        return prev;
    }

    /**
     * 区间翻转
     *
     * @param head
     * @param left
     * @param right
     */
    public static void reverseBetween(StringNode head, int left, int right) {
        if (head == null || left == right) {
            return; // 无需反转
        }

        // 创建一个虚拟头节点，简化边界条件处理
        StringNode dummy = new StringNode("虚拟节点，用于指向头部节点");
        dummy.next(head);

        StringNode pre = dummy;
        // 移动到 left 的前一个节点
        for (int i = 1; i < left; i++) {
            if (pre.next() == null) {
                System.err.println("left 超出链表长度");
                return;
            }
            pre = pre.next();
        }

        // 反转区间 [left, right]
        StringNode start = pre.next(); // 反转区间的第一个节点
        StringNode then = start.next(); // 要移动的节点

        for (int i = left; i < right; i++) {
            if (then.next() == null) {
                System.err.println("right 超出链表长度");
                start.next(then.next());
                then.next(pre.next());
                pre.next(then);
                break;
            }
            start.next(then.next());
            then.next(pre.next());
            pre.next(then);
            // 移动到下一个翻转的节点
            then = start.next();
            System.out.println("执行过程：" + head);
        }
    }

    /**
     * 合并两个排序的链表
     *
     * @param link1
     * @param link2
     * @return
     */
    public static StringNode merge(StringNode link1, StringNode link2) {
        if (link1 == null) {
            return link2;
        }
        if (link2 == null) {
            return link1;
        }
        StringNode merged = new StringNode("");
        StringNode cur = merged;
        while (link1 != null && link2 != null) {
            if (Integer.parseInt(link1.getValue()) <= Integer.parseInt(link2.getValue())) {
                cur.next(link1);
                link1 = link1.next();
            } else {
                cur.next(link2);
                link2 = link2.next();
            }
            cur = cur.next();
        }
        StringNode remain = link1 != null ? link1 : link2;
        cur.next(remain);
        return merged.next();
    }

    public StringNode next() {
        return next;
    }

    public void next(StringNode next) {
        this.next = next;
    }

    public String getValue() {
        return value;
    }

    /**
     * 添加列表，并返回当前节点
     *
     * @param val
     * @return
     */
    public void add(String val) {
        StringNode newNode = new StringNode(val);
        StringNode last = this;
        while (last.next() != null) {
            last = last.next();
        }
        last.next(newNode);
    }

    @Override
    public String toString() {
        StringBuilder s = new StringBuilder(this.value);
        StringNode cur = this;
        while (cur.next != null) {
            s.append(" -> ").append(cur.next.value);
            cur = cur.next;
        }
        s.append(" -> null");
        return s.toString();
    }
}




